package q502_findMaximizedCapital;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    /*
    IPO
    初始资金w 可以购买k次
    首先明确每次购买必然是有利润的，因此w必然增加的
    所以可以使用堆来解决
    使用一个二维数组将cap和prof绑定并按照cap从小到大排序
    之后使用一个优先队列 按照prof从大到小排序
    因此在k次购买中，每次都能够找出当前 能够买的 并且 所获得利润最大 的一支
    最终得到答案
     */
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int idx = 0, n = profits.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0; i < k; i++) {
            while (idx < n && arr[idx][0] <= w) {
                pq.offer(arr[idx][1]);
                ++idx;
            }
            if (!pq.isEmpty()) w += pq.poll();
            else break;
        }
        return w;
    }
}
